The amount of information and content available on the Internet continues to grow rapidly. Given the vast amount of information, search engines have been developed to facilitate searching for electronic documents. In particular, users may search for information and documents by entering search queries comprising one or more terms that may be of interest to the user. After receiving a search query from a user, a search engine identifies documents and/or web pages that are relevant based on the search query. Because of its utility, web searching, that is, the process of finding relevant web pages and documents for user issued search queries has arguably become the most popular service on the Internet today.
Search engines operate by crawling documents and indexing information regarding the documents in a search index. When a search query is received, the search engine employs the search index to identify documents relevant to the search query. Use of a search index in this manner allows for fast retrieval of information for queries. Without a search index, a search engine would need to search the corpus of documents to find relevant results, which would take an unacceptable amount of time.
As the Internet continues to grow, search engines continue to index larger numbers of documents. Given a large search index, some queries may take an amount of time to run that is unacceptable to users. As a result, search engines often take shortcuts when querying a search index in order to return search results back to users in a timely manner. Often, users' expectations are to receive search results within a few hundred milliseconds. To meet this constraint, some search engines may only partially evaluate search queries, which may adversely impact the quality of the search results.